#leetcode题目75：颜色分类
#难度：中等
#时间复杂度：O(n)
#空间复杂度：O(1)
#方法：双指针
#要求原地修改
from typing import List
class Solution:
    def sortColors(self, nums: List[int]) -> None:
        if not nums:
            return
        left,right=0,len(nums)-1
        i=0
        while i<=right:
            if nums[i]==0:
                nums[i],nums[left]=nums[left],nums[i]
                left+=1
                i+=1
            if nums[i]==2:
                nums[i],nums[right]=nums[right],nums[i]
                right-=1
            i+=1

#测试数据
nums=[2,0,2,1,1,0]
#预期输出：[0,0,1,1,2,2]
solution=Solution()
solution.sortColors(nums)
print(nums)    